1. Field of the Invention
The present invention relates to the field of computerized data compression and expansion, and more particularly relates to a methodology and apparatus for employing random access memories for character code compression and expansion.
2. Description of the Prior Art
Data or character code expansion and compression are widely used in the communications field to transmit or store information. One common class of methods and systems for data compression is that one which generates a mathematical combination describing the information to be transmitted and then transmits the result of the mathematical computation. The data is then expanded by a reverse mathematical computation. A second class of common data compression methods and apparatus is one in which redundant information is removed from the input data or characters. A code indicative of the amount of redundancy removed or compressed from the input codes is then transmitted along with the compressed data. A third class of data compression schemes is known which involves the addition of bits to the input data wherein the combined number represents a RAM or ROM address. The shorter or more compact address is then transmitted instead of the expanded contents which are contained at that memory address.
For example, Fox, U.S. Pat. No. 3,662,347 illustrates a compander system, namely a system that reduces the ampitude of high level signals and increases the ampitude of low level signals at the transmitter end with a reversal of the process at the receiver end. The system and method disclosed by Fox employs a read only memory that is used to expand and compress the data. An analog signal is coupled to comparator 4 in Figure 1a which is, in turn, coupled on a bit-by-bit basis to an output register 16 under the control of control register 15. Depending on the words stored in output register 16, a certain address is read from memory 8. The data stored in each location of memory 8 has a greater bit length than the data stored in output register 16. Therefore, the dynamic range of memory 8 can be greater than the stored number in output register 16. A number read from memory 8 is then reconverted into an analog signal and coupled to input 6 of comparator 4. The approximation repeats through successive cycles until each bit of the number stored in output register 16 has been set. When the number has been completely approximated it is then transmitted from output register 16. The graph of FIG. 2a in Fox shows the output and input relationships in curves 23 and 22. Curve 23 shows an expansion or enhancement of low level signals and a compression of the high level signals. What is transmitted are signals in the input range according to the mapping curves 22 or 23.
Rinaldi et al, U.S. Pat. No. 3,432,811, discloses a code convertor which accepts an eight bit word and converts it into a BCD value. The input is in pure binary form and is converted into a dual order binary coded decimal. The five bit output word consists of two orders, namely a four bit address and a fifth order bit. The binary input is converted into a first binary coded decimal output, which represents the four bit word. Since the binary input may range from 0 to 15, the output will correspond either to the decimals 0-9 or to 0-5 of a binary input in the range of 10-15. A 0 is put in the fifth order bit if the first four orders assume the decimal value of 0-9. A 1 is put into the fifth order bit if the four orders take on a value of 10-15.
Lavallee, U.S. Pat. No. 3,726,993 discloses a variety of methods of data compression wherein signals are encoded by utilizing a combination of OR gates which compresses a series of signals into a single bit. Information is encoded to remove all redundant bits. The compressed data, together with a code indicative of the state of compression, is accummulated in a memory for transmission. The information is expanded by reading the data backwards through a memory in the same order as it was encoded. Reading is controlled by the compression code. The information is progressively combined in Lavallee's apparatus in groups of combined signals and then those groups are further combined to form successfully smaller groups until a single group of combined signals is obtained.
Each of the prior art methods and apparatus for compressing and expanding information require the use of custom designed circuitry which implements a specific data compression method. As shown in Lavallee and in Rinaldi the circuitry can be quite complex. In each of the cases discussed above, the circuitry is restricted to implementing a single and very specific data compression and expansion methodology. In terms of hardware cost this complexity and this inflexibility results in a low function to cost ratio.
What is needed then is a method and apparatus which is simple in design thereby reducing the cost, increasing the reliability and minimizing on the space and complexity of electronics devoted to data compression and expansion. In addition, a methodology and apparatus is also needed which is inherently flexible and which allows for the possibility of varying the type or specie of data compression and expansion methodologies executable by a single circuit design. Further, what is needed is a methodology which can be implemented in circuitry which is of such general design that it may be time-shared or used in applications for purposes other than data compression and expansion.
These and other objects of the present invention can be better understood by considering the brief summary of the invention.